import java.util.*;
 class BinaryTree {
    static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
        TreeNode(char val){
            this.val = val;
        }
    }

    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    //前序遍历
     public void preOrder(TreeNode root){
        if(root == null)return;
         System.out.print(root.val + " ");
         preOrder(root.left);
         preOrder(root.right);
     }
     //中序遍历
     public void inOrder(TreeNode root){
        if(root == null)return;
        inOrder(root.left);
         System.out.print(root.val + " ");
         inOrder(root.right);
     }
     //后序遍历
     public void postOrder(TreeNode root){
        if(root == null)return;
        postOrder(root.left);
        postOrder(root.right);
         System.out.print(root.val + " ");
     }
     /**
      * 获取二叉树节点个数
      */
     //法一
     public int nodeSize;
     public void getNodeSize1(TreeNode root){
         if(root == null)return;
         nodeSize++;
         getNodeSize1(root.left);
         getNodeSize1(root.right);
     }
     //法二
     public int getNodeSize2(TreeNode root){
         if(root == null)return 0;
         return 1+getNodeSize2(root.left)+getNodeSize2(root.right);
     }
     /**
      * 获取叶子节点数
      */
     //法一 遍历思路
     public int leafNodeCount;
     public void getLeafNodeCount(TreeNode root){
         if(root == null)return;
         if(root.left == null && root.right == null){
             leafNodeCount++;
         }
         getLeafNodeCount(root.left);
         getLeafNodeCount(root.right);
     }
     //法二 子问题
     public int getLeafNodeCount2(TreeNode root){
         if(root == null)return 0;
         if(root.left == null && root.right == null)return 1;
         return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
     }
     /**
      * 获取第K层节点个数
      */
     public int getKLevelNodeCount(TreeNode root,int k){
         if(root == null)return 0;
         if(k == 1)return 1;
         return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
     }
     /**
      * 获取二叉树的高度
      */
     public int getHeight(TreeNode root){
         if(root == null)return 0;
         int leftHeight = getHeight(root.left);
         int rightHeight = getHeight(root.right);
         return Math.max(leftHeight,rightHeight) + 1;
     }
     /**
      * 检测值为value的元素是否存在
      */
     public TreeNode find(TreeNode root, char value){
         if(root == null){
             return null;
         }
         if(root.val == value)return root;
         TreeNode leftRoot = find(root.left,value);
         if(leftRoot != null){
             return leftRoot;
         }
         TreeNode rightRoot = find(root.right,value);
         if(rightRoot != null){
             return rightRoot;
         }
         return null;
     }
     /**
      * 判断两二叉树是否相同
      */
     public boolean isSameTree(TreeNode p, TreeNode q) {
         if(p == null && q == null){
             return true;
         }
         if(p == null && q != null || p != null && q == null){
             return false;
         }
         if(p.val != q.val){
             return false;
         }
         return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
     }
     //层序遍历
     void levelOrder(TreeNode root) {
        if(root == null)return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
     }


     // 判断一棵树是不是完全二叉树
     //用到了层序遍历
     boolean isCompleteTree(TreeNode root) {
         if(root == null)return true;
         Queue<TreeNode> queue = new LinkedList<>();
         queue.offer(root);
         while(!queue.isEmpty()){
             TreeNode cur = queue.poll();
             if(cur != null){
                 queue.offer(cur.left);
                 queue.offer(cur.right);
             }else{
                 break;
             }
         }
         while(!queue.isEmpty()){
             TreeNode cur = queue.poll();
             if(cur != null)return false;
         }
         return true;
     }
     //再写一遍，
     // 判断一棵树是否是完全二叉树
     //用到了层序遍历
     boolean isCompleteTree2(TreeNode root){
         if(root == null)return true;
         Queue<TreeNode> queue = new LinkedList<>();
         queue.offer(root);
         while(!queue.isEmpty()){
             TreeNode cur = queue.poll();
             if(cur != null){
                 queue.offer(cur.left);
                 queue.offer(cur.right);
             }else{
                 break;
             }
         }
         while(!queue.isEmpty()){
             if(queue.poll() != null){
                 return false;
             }
         }
         return true;
     }

     //反转二叉树
     public TreeNode invertTree(TreeNode root) {
         if (root == null) return null;
         TreeNode left = invertTree(root.left);
         TreeNode right = invertTree(root.right);
         root.left = right;
         root.right = left;
         return root;
     }

     //对称二叉树
     public boolean isSymmetric(TreeNode root) {
        if(root == null)return true;
        return checkSymmetric(root.left,root.right);
     }
     public boolean checkSymmetric(TreeNode leftTree,TreeNode rightTree){
         if(leftTree == null && rightTree != null ||
                 leftTree != null && rightTree == null){
             return false;
         }
         if(leftTree == null && rightTree == null)return true;
         if(leftTree.val != rightTree.val)return false;
         return checkSymmetric(leftTree.left,rightTree.right) &&
                 checkSymmetric(rightTree.left,leftTree.right);
     }

     //给定一个二叉树，判断它是否是平衡二叉树(是指该树所有节点的左右子树的深度相差不超过 1)
     public boolean isBalanced(TreeNode root) {
        if(root == null)return true;
        int leftTree = getHeight(root.left);
        int rightTree = getHeight(root.right);
        if(Math.abs(leftTree - rightTree) > 1){
            return false;
        }
        return isBalanced(root.right) && isBalanced(root.left);
     }


     //在二叉树中找出两节点的公共祖先节点
     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
         if(root == null)return null;
         if(root.left == p && root.right == q ||
                 root.left == q && root.right == p){
             return root;
         }
         if(root == p || root == q){
             return root;
         }
         TreeNode left = lowestCommonAncestor(root.left,p,q);
         TreeNode right = lowestCommonAncestor(root.right,p,q);
         if(left != null && right == null){
             return left;
         }
         if(left == null && right != null){
             return right;
         }
         if(left != null && right != null){
             return root;
         }
         return null;
     }
 }
